/*
 * =====================================================================================
 *
 *       Filename:  mysort.c
 *
 *    Description:  implement insert,shell,quick and heap sort
 *
 *        Version:  1.0
 *        Created:  2012年03月20日 16时38分19秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Regan (), lcqhigh@gmail.com
 *        Company:  
 *
 * =====================================================================================
 */

#include	<assert.h>
#include	"utility.h"
#define T int

typedef int (*CmpFunc)(T a, T b);
typedef int (*SortFunc)(T *arr, int n, CmpFunc compare);

int InsertSort(T *arr, int n, CmpFunc compare)
{
    int numCmp = 0; //统计比较次数
    int k;
    for( k = 1 ; k < n ; ++k )
    {
        T temp = arr[k];
        int i = k -1;
        for (; i >= 0; --i)
        {
            ++numCmp;
            if( compare(temp, arr[i]) < 0)
            {
                arr[i+1] = arr[i];
            }
            else
                break;
        }
        arr[i+1] = temp;
    }
    return numCmp;
}

int ShellSort(T *arr, int n, CmpFunc compare)
{
    int numCmp = 0;
    int h = 1;
    while (h <= n / 9)
        h = 3 * h + 1;

    for (; h > 0; h /= 3)
    {
        int k = h;
        for(; k < n ; ++k )
        {
            int i;
            T temp = arr[k];
            //i minus k per time
            for( i = k-h ; i >= 0 ; i -= h)
            {
                ++numCmp;
                if( compare(temp, arr[i]) < 0 )
                {
                    arr[i+h] = arr[i];
                }
                else
                {
                    break;
                }
            }
            arr[i+h]  = temp;
        }
        
    }
    return numCmp;
}


int compfunc(int a, int b)
{
    return a - b;
}

//find the first occurance of 
int mybsearch(T x[], int low, int high, T target)
{
    assert(low >= 0 && high >= 0 && high >= low);
    int mid;
    //assume x[low] < target <= x[high] ,the termination of the loop is low + 1 = high
    --low;
    while (low + 1 < high)
    {
        mid = (high - low) / 2 + low;
        if (target > x[mid])
            low = mid;
        else
            high = mid;
    }
    if (x[high] == target)
        return high;
    return -1;
}

static inline void swapValue(T *x, T *y)
{
    T temp = *x;
    *x = *y;
    *y = temp;
}

/**************************quick sort******************************************/
static size_t qsortcmptimes = 0;
size_t getPivot(T *x, size_t n, CmpFunc compare)
{
    size_t pLeft = -1, pRight = n - 2;
    if (n > 2)
    {
        size_t mid = abs(rand()) % n;
        if (mid < 1 || mid > n - 2)
            mid = 1;
        //随机寻找枢轴
        T *y[3] = {x, x+mid, x+n-1};
        ++qsortcmptimes;
        if (compare(*y[0], *y[1]) > 0) {
            swapValue(y[0], y[1]);
        }
        ++qsortcmptimes;
        if (compare(*y[1], *y[2]) > 0) {
            swapValue(y[1], y[2]);
            ++qsortcmptimes;
            if( compare(*y[0], *y[1]) > 0 )
                swapValue(y[0], y[1]);
        }

        ++qsortcmptimes;
        swapValue(&x[mid], &x[n-2]); //now we know that x[0] <= x[n-2] <= x[n-1]
        //use sentinals 
        for (;;) {
             while( compare(x[++pLeft], x[n-2]) < 0 )
                    ++qsortcmptimes;
             while( compare(x[--pRight], x[n-2]) > 0 )
                    ++qsortcmptimes; 
             if (pLeft >= pRight)
                 break;
             swapValue(&x[pLeft], &x[pRight]);
        }
        swapValue(&x[pLeft], &x[n-2]);
    }
//    else if (n == 2 && x[0] > x[1]) 
//    {
//        swapValue(x, x+1);
//        pLeft = 1;
//    }
//    else
//        pLeft = 0;

    return pLeft;
}

int myqsort(T *x, int n, CmpFunc compare)
{
    while (n > 10)
    {
        //get the index of the pivot
        size_t pivot = getPivot(x, n, compare);
        size_t numGE = n - pivot - 1;
        if (numGE < pivot)
        {
            myqsort(x+pivot+1, numGE, compare);
            n = pivot;
        }
        else 
        {
            myqsort(x, pivot, compare);
            x += (pivot+1);
            n = numGE;
        }
    }

    if (n > 1)
    {
        int cmptimes = InsertSort(x, n, compare);
        //printf ( "in insert sort n=%d, x=%p, timesCmp=%d\n", n, x, cmptimes);
        qsortcmptimes += cmptimes;
    }
    return 0;
}

/*****************************heap sort*************************************/
size_t heapCmpTimes = 0;
void heapdown(T *x, size_t pos, size_t endpos, CmpFunc compare)
{
    size_t savedpos = pos;
    size_t i = 2 * pos + 1;
    //shift down to the leaf
    for (; i <= endpos; i = 2 * pos + 1)
    {
        ++heapCmpTimes;
        if (i < endpos && compare(x[i+1], x[i]) > 0)
            ++i;
        swapValue(&x[i], &x[pos]);
        pos = i;
    }

    while (1)
    {
        i = (pos -1) / 2;
        ++heapCmpTimes;
        if (pos <= savedpos || compare(x[i], x[pos]) > 0)
            break;
        swapValue(&x[pos], &x[i]);
        pos = i;
    }
}

int heapsort(T *x, int n, CmpFunc compare)
{
    heapCmpTimes = 0;
    int k = (n-1)/2;
    for (; k >= 0; --k)
        heapdown(x, k, n-1, compare);

    while (--n)
    {
        swapValue(&x[n], &x[0]);
        heapdown(x, 0, n-1, compare);
    }
    return heapCmpTimes;
}
/* ********************************************************************* */

void reverseArr(T *x, size_t n)
{
    int i, k;
    for( i = 0, k = n-1 ; i < k ; ++i, --k )
    {
        T temp = x[i];
        x[i] = x[k];
        x[k] = temp;
    }
}

void test()
{
    T list[1064];
    int cnt = 0;
    SortFunc sortfunc  = heapsort;//myqsort;//InsertSort;//ShellSort; 
    int numCmp = 0, totalCmp = 0;
    int listsize = sizeof(list) / sizeof(list[0]) - 1;
    //printf ( "The first address of the list is %p\n", list );
    for (; cnt < 5; ++cnt)
    {
        genRandInt(list, listsize);
        printf ( "before sort:\n" );
        printIntarr(list, listsize);
//        InsertSort(list, listsize, compfunc);
//        reverseArr(list, listsize);
        printf ( "after sort:\n" );
        numCmp = sortfunc(list, listsize, compfunc);
        totalCmp += numCmp;
        printIntarr(list, listsize);
        int k = 0;
        for (; k < listsize; ++k)
        {
            assert(k == mybsearch(list, 0, listsize-1, list[k]));
        }
    }
    printf ( "all compare %lf times\n", 1.0 * totalCmp / cnt );
}

int main(int argc, char *argv[])
{
    test();
    return 0;
}
